Authentication protocols are used in contemporary communication systems for enabling a first party to prove its identity towards a second party; for convenience, these first and second parties are conveniently denoted by prover and verifier respectively. In many known protocols, the prover first claims an identity, after which the prover proves knowledge of some secret associated with the prover's claimed identity. A protocol in which two parties are being assured of each other's identity is referred to as “mutual authentication”. Such authentication is often implemented using key establishment procedures, for example using public-private key authentication protocols. These authentication protocols not only verify identity, but also often establish symmetrical session keys with which further communications can be encrypted and authenticated.
The inventors have appreciated that it is desirable that identities of mutually communicating parties cannot be determined by third parties observing or eavesdropping on the mutually communicating parties. Such a situation can potentially arise in practice when a user authenticates herself using a wireless smart card presented to a smart card reader, for example a smart card reader at an entrance of a high-security building. If a standard authentication protocol is employed at the entrance, an eavesdropper could hypothetically simply detect the presence of a user at this location. Such detection can potentially provide essential initial information for executing location tracking of the user. Moreover, this location tracking can constitute an invasion of personal privacy.
This problem has already been envisaged by Martin Abadi in a scientific paper with title “Private Authentication” presented at a Conference on Privacy Enhancing Technologies (PET2002), San Fracisco, USA, Apr. 2002 whose proceedings are published in Springer Lecture Notes in Computer Science vol. 2482/2003, pp. 27-40. In the paper, M. Abadi describes two protocols which are variants of known Denning-Sacco and Needham-Schroeder protocols as elucidated in B. Schneier publication “Applied Cryptography”, Second Edition published by John Wiley & Sons Inc. in 1996. A problem of these recently proposed protocols by M. Abadi is that public key cryptography is employed requiring a relatively large amount of processing power for its implementation, such processing power often not being practical and/or available on small consumer devices, for example portable battery-powered devices.
A more recent polynomial-based multi-user key generation and authentication method is described in a published international PCT patent application WO 03/077470 (attorney docket PHNL020192). In this PCT application, there is described a method of generating a common secret between a first party and a second party. These parties can be, for example, devices in a home network operable in accordance with a contemporary Digital Rights Management (DRM) framework. The devices calculate the common secret by evaluating a product of two polynomials P(x, y) and Q(x, z) using parameters previously distributed by a Trusted Third Party (TTP) and parameters obtained from another device. Optionally, each party subsequently verifies that the other party has generated the same secret using a zero-knowledge protocol or a commitment-based protocol. Such a method described in this published PCT application is especially suitable for use in conjunction with low power devices such as Chip-In-Disc type devices. The inventors have appreciated that even this recent authentication method has drawbacks and limitations which the inventors seek to address by way of the present invention.